/* 
  使用master公式计算时间复杂度:O(N*logN)
  归并排序:
    思路: 先让左侧排好序,再让右侧排好序,然后整合(merge操作)
    merge操作思路: (左右两侧排好序后)
    1. 准备一个辅助空间ret
    2. 从左侧开始,左右两侧数据进行比较,左侧小于等于右侧拷贝左侧,反之拷贝右侧,放进ret
    3. 直到某一侧的索引他的的范围,将另一侧剩余的数据全部拷贝放进ret
    4. 最后返回这个ret
*/

function mergeSort(arr) {
  if (!arr || arr.length < 2) {
    return
  }
  process(arr, 0, arr.length - 1)
}
function process(arr, L, R) {
  if (L == R) {
    return
  }
  let mid = L + ((R - L) >> 1)
  process(arr, L, mid)
  process(arr, mid + 1, R)
  merge(arr, L, mid, R)
}
function merge(arr, L, M, R) {
  let temp = [],
    p1 = L,
    p2 = M + 1,
    i = 0
  while (p1 <= M && p2 <= R) {
    temp[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++]
  }
  while (p2 <= R) {
    temp[i++] = arr[p2++]
  }
  while (p1 <= M) {
    temp[i++] = arr[p1++]
  }
  for (let i = 0; i < temp.length; i++) {
    arr[L + i] = temp[i]
  }
}
let arr = [1, 4, 5, 9, 0, 2, 6, 3, 7]
mergeSort(arr)
console.log(arr)
